package link_list

// https://leetcode.cn/problems/partition-list/ leetcode-86
func partition(head *ListNode, x int) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	dummyNode := &ListNode{Next: head}
	var flag, flagPrev *ListNode
	prev := dummyNode
	for node := head; node != nil; {
		if node.Val >= x && flag == nil {
			flag = node
			flagPrev = prev
		}

		if node.Val < x && flag != nil {
			next := node.Next
			prev.Next = next
			flagPrev.Next = node
			node.Next = flag
			flagPrev = flagPrev.Next
			node = next
			continue
		}
		node = node.Next
		prev = prev.Next
	}
	return dummyNode.Next
}
